1. Field of the Invention
The present invention is directed to memory devices and, more particularly, to content addressable memories (CAMs).
2. Description of the Background
A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information, i.e., either logic zero or logic one. The bits stored within a row of memory cells constitute a CAM word. During compare operations, a comparand word is received from an input bus and then compared with all the CAM words. For highest performance, conventional CAM architectures simultaneously compare all of their pattern entries with the input bus. For each CAM word that matches the comparand word, a corresponding match line signal is asserted to indicate a match condition. When there is a match condition, the index or address of the matching CAM word is read from the CAM. Associative information stored in, for instance, an associated RAM, may also be provided. Because CAMs provide a mechanism that enables matches to be quickly located, CAMs have come to be used in devices, such as routers.
Routers are used in interconnected computer networks, such as the Internet, to couple networks together. Such a computer network router is typically connected to two or more distinct networks. For a message sent from one network to another destination network, the router receives the message, in the form of data packets, from one of the networks to which the router is connected and searches a database of routing information to determine to which of the connected networks the data packet should next be sent so that the data packet can reach the destination network. The database of routing information can be quite large in networks composed of many different interconnected networks, such as the Internet. Within each router, routing information received from neighboring routers is used to update its own routing table. That table is then used to control how packets are routed from one neighboring router to another on the network. Because CAMs use dedicated parallel hardware for comparisons, they are ideal for use in routers and other high performance systems.
An Internet protocol (IP) address size is a fixed width for a particular protocol, so a prefix length must be less than or equal to the IP address size. The CAM effectively compares an incoming IP address with all of its contents to find a match. The number of prefix bits can be specified independently for each routing table entry, so lower address bits are ignored within each CAM entry during comparisons. The simplest way to implement that behavior in a CAM is to use a ternary CAM (TCAM) that can be programmed to match entries with a 0, 1 or X (don't care) at each bit position within each CAM entry.
In cases where a TCAM input results in matches found with multiple entries having different prefix lengths, the routing rules require that the match with the longest prefix length is chosen. In the case where only one match is possible for any input pattern, the order in which entries are placed in the TCAM does not matter, as they are all normally compared with the input. When multiple TCAM matches are possible, the simplest way to prioritize matches is on the address at which entries are written into the TCAM. For example, if the TCAM prioritizes entries at its higher programming addresses, then the TCAM loading algorithm can sort data by prefix length to ensure that longer prefix entries are written to the TCAM at a higher address than shorter prefix entries. In IP routing tables, it is not permitted to have identical matching prefix values of the same prefix length.
A known problem with CAMs is that entry miss-matches are far more common than matches, so match lines are usually charged and discharged on every access. As described below in conjunction with FIG. 6, that makes CAM power consumption relatively high compared with other storage devices.
FIG. 6 shows a typical CAM row 10 as having n CAM cells 12(1)-12(n) each coupled to an associated match line ML. A pull-up transistor 14, coupled between a supply voltage VDD and match line ML, has a gate tied to ground potential, and therefore remains in a conductive state. Prior to each compare operation between an n-bit comparand word and an n-bit CAM word stored in CAM cells 12(1)-12(n), match line ML is pre-charged to supply voltage VDD via pull-up transistor 14. The n-bits of the comparand word are compared with corresponding bits of the CAM word in respective CAM cells 12(1)-12(n). If all bits of the comparand word match corresponding bits of the CAM word, the match line ML remains charged to indicate a match condition. Conversely, if one of the comparand bits does not match the corresponding CAM bit, the CAM cell 12 storing that CAM bit discharges match line ML toward ground potential to indicate a mismatch condition.
The match lines in a CAM array are typically pre-charged to the supply voltage VDD for each and every compare operation. Thus, for each mismatch condition, an associated match line ML is first charged toward VDD and then discharged toward ground potential. Current flow associated with this charging and discharging results in undesirable power consumption. Further, as the number of CAM cells in each row of a CAM array increases, capacitive loading on the match lines increases accordingly. As loading on the match lines increases, the current required to charge the match lines toward the supply voltage increases. Accordingly, as CAM words are widened, for example, to accommodate longer Internet addresses, power consumption resulting from charging the match lines during compare operations may significantly increase. Furthermore, because mis-matches are far more common than matches, as internet Addresses are lengthened and CAM words widened, power consumption increases substantially. Therefore, the need exits for a circuit architecture that reduces the power consumed by the CAM.